The performance of applications, such as real-time interactive multimedia applications, is dependent on task scheduling. Scheduling tasks in a real-time interactive multimedia application is difficult because of the requirement for integration of task and data parallelism for effective computation. Task and data parallelism are distinct programming models for describing parallel applications.
A task parallel application is typically composed of a set of cooperating processes which are implemented in a framework such as POSIX threads. The programmer explicitly specifies communication and synchronization between threads in the application. The run-time system then schedules the execution of the threads on the processor. In contrast, a data-parallel application is usually a single program which executes on multiple processors and operates on distributed data.
Tasks in an application may be scheduled using one of three prior art classes of scheduling algorithms for parallel systems. The first class is off-line schedulers for an application. An off-line scheduler for an application is described in “Compilation of Parallel Multimedia Computations—Extending Retiming Theory and Amdahl's law” by Prasanna, Proc. Symposium on Principles and Practice of Parallel Programming (PPOPP), 1997. This off-line scheduler performs extensive analysis to optimize a single static schedule for an application. Some applications are dynamic in the sense that the relative execution times for the tasks vary over time. Dynamic applications are not efficiently executed by a single static schedule.
The second class is on-line schedulers for a mix of applications. This class includes systems such as described in “The Design, Implementation and Evaluation of Smart: A Scheduler for Multimedia Applications” by Nieh et al., Proceedings of the Sixteenth ACM Symposium on Operating System Principles (SOSP), 1997 and “Adaptive Rate-Controlled Scheduling for Multimedia Applications” by Yau et al., Proc. 8th Symposium on Parallel Algorithms and Architecture (SPAA), June 1996. These systems are very general and do not involve detailed analysis of the applications to be scheduled.
The third class of scheduling is the real-time scheduling algorithms used, for example, in commercial real-time operating systems such as VxWorks. These algorithms schedule tasks such that each operation completes within a bounded amount of time and is described in “Scheduling Algorithms” by Bruker, Springer-Verlang, 1995 and “Scheduling: Theory, Algorithms, and Systems” by Pinedo, Prentice Hall, 1995.